package _11_整理题目._4_动态规划._买卖股票;


import org.junit.Test;

import java.util.Arrays;

/**
 * 假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。
 * 你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。
 * 请你设计一个算法来计算可以获得的最大收益。
 * 例如：输入 [1,4,2]，返回值 3
 *
 * 1、暴力搜索计算，O(n^2) O(1)
 *
 * 2、动态规划，O(n) O(n)
 *      dp[i] 表示在第 i 天卖出获得的最大利润，需要保存之前的 最小股票值
 *      max (dp[i]) 即是最大利润
 *
 * 3、动态规划优化空间，O(n) O(1)
 *
 */
public class _02_买卖股票的最好时机 {
    
    public int maxProfit1(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int profit = prices[j] - prices[i];
                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }
        }
        return maxProfit;
    }

    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int minPrice = prices[0];
        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            dp[i] = prices[i] - minPrice;
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public int maxProfit3(int[] prices) {
        int n = prices.length;
        int minPrice = prices[0];
        int maxProfit = 0;
        for (int i = 0; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i]-minPrice);
        }
        return maxProfit;
    }

    @Test
    public void main() {
        int[] input = {1, 4, 2};
        assert maxProfit1(input) == 3;
    }
    
}
